Add, compare and select circuits (ACS) are used in digital sequence detectors to determine the most likely sequence of digital signals corresponding to a sequence of received signals. The received signals are compared to a variety of idealized signal sequences to determine which idealized sequence compares signal sequences to determine which idealized sequence compares most closely. In that manner the accurate detection of a sequence of received signals can be achieved. Sequence detectors may be used in many applications and will be illustrated herein in the context of a digital computing system with magnetic storage.
In digital systems, magnetic media is used to archive data and used for the interactive processing of data with the central processing unit and semiconductor memory elements. Drive electronics units for magnetic storage devices provide an interface to the host system and receive data from the host to be written to the magnetic media. The drive units also process and present data to the host that has been read from the magnetic storage media. A magnetic transducing head is connected to the drive electronics unit and is situated in close proximity to the magnetic media in order to write data to the media or read data from the media. Significant effort has been made to pack data ever more densely on the media while at the same time improving the write and read control functions to approach error-free operation. In the effort to produce dense recording and error-free retrieval, digital channels with sequence detectors have been developed to view a multi-sample period of the readback waveform produced by the transducing head. That multi-sample period is compared to an expected set of samples which correspond to various idealized data sample patterns. The detector operates to accumulate error signals with respect to the various data sample patterns and by determining the least error is able to recognize the most likely idealized data sample pattern corresponding to the received signals. A sequence detector of this type is described in the aforementioned U.S. patent application Ser. No. 07/852,015 incorporated herein by reference.
Limiting factors in packing data onto the magnetic media are frequently associated with the readback operation where the magnetic transition results in an electrical pulse in the head which is transferred from the head to the drive electronics unit for amplification and detection. The pulse signals at the head are difficult to detect accurately since they are small and subject to obfuscation. In general, as magnetic transitions are more densely packed on the media the accurate reading of those transitions is more sensitive to distortion, timing variations and noise.
In order to improve the capability of accurately detecting densely packed data, sequence detectors have been developed for use in read channel circuits. As mentioned above, sequence detectors involve the accumulation of error data in viewing a sequence of received data samples. Circuits utilized to perform the operation include add, compare and select (ACS) circuits. Unfortunately, the ACS circuits can themselves be a limiting factor on the ability to pack data more densely on magnetic media because of the time needed for the ACS circuits to process the received data. Accumulated error value is indicative of the total amount of noise in a system and to accurately reflect the error value in a noisy system can result in binary numbers many bits in length, in one implementation 13 bits in length. In order to recognize the data bit pattern with the least accumulated error, 13 bit numbers are subtracted from each other to determine the least quantity. Since adding (or subtracting) multi-bit numbers is a time consuming process, the add, compare, select circuit itself becomes a limiting factor on the ability of a system to pack data on the magnetic media.
It is an object of this invention to modify ACS circuits for use in a sequence detector to optimize the time needed to identify the idealized pattern representing closest match to the received pattern.
As mentioned above, digital information is frequently stored by recording patterns of magnetization on a surface such as a magnetic disk or tape. A recorded magnetization pattern induces a time varying electrical response signal in a sensor or read head as the magnetic pattern moves past the read head. The resulting signal is processed electronically to reconstruct the bits of the digital information stored on the disk or tape. The heads are positioned close to the magnetic surface. When the magnetic surface is moved under the head, the head responds to the magnetic flux from the magnetized medium so that a voltage pulse is produced each time the head encounters a transition in the direction of magnetization of the medium.
Successive magnetic transitions along a track necessarily alternate in polarity. A transition from north to south magnetization is followed by a transition from south to north. The polarity of the voltage pulses induced in the read head alternate from plus to minus with the polarity of the transitions.
Ideally, the pulses induced in the read head would be impulse functions of infinite amplitude, zero width, and some finite energy. In reality, there are band width limiting factors in the write process, in the recording medium, and in the read process which produce a pulse of finite amplitude and width. The shape of the pulse is determined by many factors including the geometry of the head, distance between head and medium, magnetic properties of the medium and the head, etc.
To prepare a sensed analog pulse train produced by the head for processing by a sequence detector, the signals are amplified, filtered and shaped. The analog pulse train is then sampled at particular discrete time intervals after which the sample train may continue to be filtered before the samples are presented to the sequence detector.
FIG. 1 shows an idealized isolated pulse 9 with the associated discrete time samples R.sub.0 through R.sub.5. In setting up the system with a programmable sequence detector like that described in U.S. patent application Ser. No. 07/052,015, one of the digital sample values is scaled to be represented by an arbitrary value, for example a "1", the other digital samples taking a ratio thereto. In FIG. 2, four samples are taken to represent the pulse: samples a, b, 1 and c, with a, b and c each being separate programmable values. Any desired number of samples can be taken relative to the width of the pulse although at the current time the number of samples taken is usually either 2, 3 or 4. In the idealized form for the four sample system shown in FIG. 3, b equals 1 and a and c each equal one-third.
When signal transitions are packed together on magnetic media, the sample values presented to the sequence detector are combinations of the packed adjacent pulses. For example, if pulses are constrained by a run-length limited code where d =1, adjacent "one" pulses in the encoded data are stored with an interposed zero pulse. Consequently, idealized sample values for two adjacent pulses are as follows (sample rate is equal to the channel bit rate):
______________________________________ R.sub.0 R.sub.1 R.sub.2 R.sub.3 R.sub.4 R.sub.5 R.sub.6 ______________________________________ Pulse 1: 0 a b 1 c 0 0 Pulse 2: 0 -a -b -1 -c combined 1 + 2: 0 a b 1 - a c - b -1 -c ______________________________________
As mentioned above, when a magnetic transition occurs, the polarity of the induced electrical signal changes. Note that for the combined pulse 1 and pulse 2 idealized samples, the positive pulse may be identified by the presence of the position "1" value occurring at sample time R.sub.3 and the negative going pulse may be identified by the presence of the negative "1" value occurring at sample time R.sub.5. Thus, the presence of a "1" in the idealized sample value is used to identify the presence of a magnetic transition and therefore a change in electrical polarity. In the data detection circuits, the "1" values are translated as defining the rise of a digital pulse on a first clock and the fall on the second clock.
FIG. 2 illustrates a received signal waveform 15 with two directly adjacent pulses separated by an interposed zero pulse. The received sample values R.sub.0 -R.sub.6 are compared to the idealized sample values in a sequence detector to determine the best match. For example, received sample value R.sub.3 might be compared to idealized sample value "1" as part of the process to determine whether an isolated pulse 1 is present. R.sub.3 might also be compared to the idealized sample value "-a" as part of the process to determine whether an isolated pulse 2 is present. And R.sub.3 might be compared to the idealized sample value "1-a" as part of a process to determine whether two directly adjacent pulses such as shown in FIG. 2 are present.
FIG. 3 shows the state diagram for a ten-state sequence detector such as described in the above-mentioned patent application. The detector of FIG. 3 is organized to reflect all possible states into which it can arrive. For example, the diagram shows that it can arrive at state 8 through either a transition from state 1 or a transition from state 4. In determining which of the transitions is most likely, the received sample signal is compared to the expected sample value of "a-c" and the difference is an error that is added to the previous error tally associated with node 1. In this case, the received sample signal is also compared to the expected sample value "a" and the difference is an error that is added to the error tally associated with node 4. The accumulated errors for each of the two paths are totaled and compared. Only the most likely path (the one with the smallest error total) is retained in a path memory as the error tally for state 8.
A subsequent received sample signal will move the state of the sequence detector from state 8 to state 9 and the value of that subsequent received sample signal is compared to an expected sample with a value of "b" as shown in FIG. 3 That difference is an error, called a "branch metric", and is accumulated with the path error for state 8 to total a new "path metric", that is the error tally associated with state 9.
FIG. 4 is a different way of illustrating the state diagram shown in FIG. 3 in which the various states are vertically disposed and the transitions between the states form a lattice network. For example, if the current state is state 8, an inspection of the state diagram shows that arrival at state 8 can be from either state 1 or state 4. The ACS circuit associated with node 8 will therefore compare the received sample signal R.sub.1 with the expected value of "a" should the entry to state 8 be from state 4, and an expected value of "a-c" for the path from state 1. Each of these error quantities, the branch metric, is added to the accumulated error, the path metric, for the respective previous states. For example, the branch metric representing the difference between the received sample signal R.sub.1 and "a-c" is added to the accumulated error, path metric PM.sub.1, associated with state 1. The branch metric representing the difference of the sample signal R.sub.1 minus "a" is added to the accumulated error, that is the path metric PM.sub.4, for state 4. The mathematical expressions for these operations are as follows: EQU PM.sub.1 +[R.sub.1 -(a-c)].sup.2 =the new path metric from state 1.(1) EQU PM.sub.4 +(R.sub.1 -a).sup.2 =the new path metric from state 4.(2)
The new path metrics, which are both possible path metrics for arriving at state 8, are compared in the ACS circuit to find which is the least. The least is stored as the path metric for state 8 and the other is discarded.
To determine the most likely path through the state diagram shown in FIG. 3, ACS circuits are associated with each of the 10 states for that sequence detector. The above-mentioned patent application reveals techniques for minimizing the number of ACS circuits associated with the sequence detector by combining certain states into a single node and generating one ACS circuit for that combination of states. The current invention can be utilized with the "folded" sequence detector of the above-mentioned patent or with an "unfolded" sequence detector such as shown in FIG. 3.
In a folded state machine such as described in the above-mentioned patent application, the idealized sample value to be compared with the received signal can be either positive or negative. With reference to FIG. 3, note that one ACS circuit can be used for both states 8 and 3 according to the teachings of the above-referenced patent application, with "+a" being the idealized sample value I.sub.X when the detector arrives at state 8 from state 4 and "-a" being the idealized sample value I.sub.X when the detector arrives at state 3 from state 7. As a consequence, there must be a .+-. sign in the generalized expression for determining the error from the ideal sample value I.sub.X. The expression is shown below. EQU (R.+-.I.sub.X).sup.2 =R.sup.2 .+-.2I.sub.X R+I.sub.X.sup.2 ( 3)
Again with reference to FIG. 3, note that "a-c" is the idealized sample value Iy leading into state 8 from state 4 and that "c-a" is the idealized sample value I.sub.Y leading into state 3 from state 10. Therefore, the generalized expression for the folded detectors utilizing the alternate path with idealized sample value I.sub.Y is: EQU (R.+-.I.sub.Y).sup.2 =R.sup.2 .+-.2I.sub.Y R+I.sub.Y.sup.2 ( 4)
In comparing these two quantities, if the expression for the idealized quantity I.sub.Y is subtracted from the idealized expression for I.sub.X it may be noted that the R.sup.2 term drops out and that the values I.sub.X.sup.2 and I.sub.Y.sup.2 are known constants. It may also be noted that upon receiving the signal R, the value RIx can be calculated and stored as can the value RI.sub.Y. Therefore, upon arrival at either state 3 or state 8, registers within the ACS circuit will contain the values RI.sub.Y, I.sub.Y.sup.2, RI.sub.X and I.sub.X.sup.2. Unfortunately, however, the .+-. sign in the above expressions cannot be determined prior to entering the node and therefore, the addition of the quantities I.sub.X R and I.sub.X.sup.2 cannot be pipelined ahead of time. Similarly, the value I.sub.Y R cannot be added to I.sub.Y.sup.2 ahead of time. This complication acts to increase the time needed to accomplish the ACS operation in a folded sequence detector resulting in additional value for the time-saving approach of this invention, described hereinafter.
Note that once the .+-. sign is determined, that defines the node as representing either state 3 or state 8. A "sign control bit" is associated with each node in order to keep track of which state the node currently represents. In the example described above, a negative sign control bit (1) indicates state 3, i.e., -I.sub.X and -I.sub.Y, while a positive sign control bit (0) indicates state 8, i.e., +I.sub.X and +I.sub.Y. The node contains a register for storing the sign control bit as well as a register for storing the path metric.
FIG. 5 illustrates a sequence detector with a received sample value, R, at the input of the detector. The sample value R represents a discrete time sample of the signal that has been read from the magnetic storage medium and then amplified, shaped, filtered and sampled to provide a sample value to the sequence detector which is recognizable by it. The received sample R is processed by the various add, compare and select modules (ACS) 10-13, so that the received sample is compared to each of the possible expected sample values. Each one of the comparisons results in an error signal of some finite amplitude. Error sums are totaled for each of the possible paths leading into each state, and one of the possible paths is chosen as a survivor for each state. Therefore, the function of the various ACS circuits is to identify the most probable path leading into the state represented by the ACS unit. The accumulated error value from each state is stored in the multi-bit path metric register of the ACS unit and comparison decisions are stored in the path memory circuit 14. After a sufficient number of samples have been received, circuit 14 will estimate the channel bit most likely associated with the received sample R, together with its surrounding sample, and produce an output signal, S, the estimated channel bit.